package lanQiaoBei.数学知识.欧拉函数;
import java.io.*;
import java.util.*;
/*欧拉函数（N*(1-1/p1)*(1-1/p2)*....）(快速求出1-N中与N互质的个数)
给定 n 个正整数 ai，请你求出每个数的欧拉函数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围

1≤n≤100,
1≤ai≤2×1e9

输入样例：

3
3
6
8

输出样例：

2
2
4
* */
public class P1 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    final static int N=110;

    static void scan()throws Exception{

    }
    public static void main(String[]args)throws Exception{
           int n=Integer.parseInt(br.readLine());
           while(n-->0){
                int x=Integer.parseInt(br.readLine()),res=x;
                for(int i=2;i<x/i;i++){
                    if(x%i==0){
                        while(x%i==0){
                            x/=i;
                        }
                        res=res*(i-1)/i;
                    }
                }
                if(x>1)res=res*(x-1)/x;
                System.out.println(res);
           }
    }
}
